class BinaryTree<T> {
  value: T;
  left: BinaryTree<T> | null;
  right: BinaryTree<T> | null;

  constructor(value: T) {
    this.value = value;
    this.left = null;
    this.right = null;
  }

  insert(value: T): void {
    if (value < this.value) {
      if (!this.left) {
        this.left = new BinaryTree(value);
      } else {
        this.left.insert(value);
      }
    } else {
      if (!this.right) {
        this.right = new BinaryTree(value);
      } else {
        this.right.insert(value);
      }
    }
  }

  search(value: T): BinaryTree<T> | null {
    if (value === this.value) {
      return this;
    } else if (value < this.value) {
      if (this.left) {
        return this.left.search(value);
      } else {
        return null;
      }
    } else {
      if (this.right) {
        return this.right.search(value);
      } else {
        return null;
      }
    }
  }

  remove(value: T): void {
    if (value < this.value) {
      if (this.left) {
        this.left.remove(value);
      }
    } else if (value > this.value) {
      if (this.right) {
        this.right.remove(value);
      }
    } else {
      if (!this.left && !this.right) {
        // 如果是叶子节点，直接删除
        this.value = null as unknown as T; // 使用类型断言将 null 赋值给 T 类型的变量
      } else if (!this.left) {
        // 如果只有右子节点，将父节点的左子节点指向右子节点
        this.value = this.right!.value;
        this.right = this.right!.right;
        this.left = this.right!.left;
      } else if (!this.right) {
        // 如果只有左子节点，将父节点的右子节点指向左子节点
        this.value = this.left.value;
        this.left = this.left.left;
        this.right = this.left!.right;
      } else {
        // 如果有两个子节点，找到右子树的最小值，将其替换当前节点的值，然后删除右子树的最小值
        const minNode = this.right.findMin();
        this.value = minNode.value;
        this.right.remove(minNode.value);
      }
    }
  }
           
  findMin(): BinaryTree<T> {
    if (!this.left) {
      return this;
    } else {
      return this.left.findMin();
    }
  }

  findMax(): BinaryTree<T> {
    if (!this.right) {
      return this;
    } else {
      return this.right.findMax();
    }
  }
}
